#!/usr/bin/python -S
"""
parse_nodes.py

Nodes for the parser.  They take an input stream of TOKENS, which are

(ID, TYPE, value) triples.

In most cases, ID doesn't need to be used.  But if you need positional
information, you can look it up with the ID.

TODO: This is a copy of execute.py.  Do you still need that?


TODO: This should be used to PARSE a CRE.

Take as input:

  DIGIT+ [a-z _]*

This should be parsed into:

  (Sequence
    (Plus DIGIT)
    (Star (Class (RANGE a z) _))

That can be turned into a tree of classes.  Those should go into cre_nodes.py.

CRE -- consistent regular expression
RPE -- Recursive descent Parser Expression.  This is a syntax that defines a
recursive descent parser.  Like parsing expression grammars, but no token-level
stuff.


"""

import sys


class Error(Exception):
  pass

# Signature of these functions:
#
# Args:
#   s, pos: input
#   trace: trace object for debugging.
#
# Return:
#   result: Captured result.  None if there was no match.  '' and {} are valid
#       captures, so make sure to use "is None" and "is not None".
#   pos: New position.


class Matcher(object):
  """Base class."""

  def __init__(self):
    pass
  
  def log(self, trace, msg, *args):
    msg = self.__class__.__name__ + ' ' + msg
    trace.log(msg, *args)

  # __str__ ?

  def Match(self, tokens, pos, trace):
    raise NotImplementedError


class TokenRef(Matcher):
  """
  Match a reference to a literal token.
  """

  def __init__(self, name):
    """
    """
    self.name = name

  def Match(self, tokens, pos, trace):
    # Out of range
    if pos >= len(tokens):
      return None, pos

    t = tokens[pos]
    #print 'TOKEN', repr(t)
    token_type, value, _ = t

    # e.g. we are a reference to 'PLUS'.  If the incoming token looks like
    # (3, 'PLUS', None), then we are a match.
    self.log(trace, '%s = %s?' % (token_type, self.name))
    if token_type == self.name:
      return t, pos + 1   # advance 1 token
    else:
      return None, pos


class Dot(object):
  """Match any token, except at end of stream."""
  ARITY = 0

  def Match(self, tokens, pos, trace):
    if len(tokens) > pos:
      return tokens[pos], pos + 1
    else:
      return None, pos


class _Multi(Matcher):

  def __init__(self, children):
    assert isinstance(children, list), children
    self.children = children


class Choice(_Multi):
  """Ordered choice.

  Returns (captured, pos).

  'captured' is a tuple of (index of clause, match), or None if there was no
  match.
  """
  def Match(self, tokens, pos, trace):
    trace.push()
    for i, c in enumerate(self.children):
      result, newpos = c.Match(tokens, pos, trace)
      #self.log(trace, '%s -> %r %r', c, result, newpos)
      if result is not None:
        trace.pop()
        return (i, result), newpos
    trace.pop()
    return None, pos


class Seq(_Multi):

  def Match(self, tokens, pos, trace):
    results = []
    trace.push()
    #self.log(trace, 'Seq %s', self.children)
    for c in self.children:
      assert c is not True, self.children
    for c in self.children:
      #self.log(trace, '-> c %s', c)
      result, newpos = c.Match(tokens, pos, trace)
      self.log(trace, '%s -> %r %r', c, result, newpos)
      if result is None:
        trace.pop()
        #self.log(trace, 'aborting Seq')
        return None, pos  # TODO: what position to return
      # True means we didn't match something
      if result is not True:
        results.append(result)
      pos = newpos
      #self.log(trace, '<- c %s', c)
    trace.pop()
    return results, pos


class _Single(Matcher):
  ARITY = 1

  def __init__(self, child):
    self.child = child


class Question(_Single):
  """Match 0 or 1."""

  def Match(self, tokens, pos, trace):
    result, newpos = self.child.Match(tokens, pos, trace)
    if result is not None:
      return result, newpos
    else:
      return [], pos  # 0-length match.


class Star(_Single):
  """Match 0 or more."""

  def Match(self, tokens, pos, trace):
    results = []
    trace.push()
    self.log(trace, '%s', self.child)
    while True:
      result, newpos = self.child.Match(tokens, pos, trace)
      self.log(trace, '-> %r %r', result, newpos)
      #print 'Star got -> %r %r' % (result, newpos)
      if result is None:  # stopped matching
        trace.pop()
        return results, pos

      if result is not True:  # success without capture
        results.append(result)
      pos = newpos


class Plus(_Single):
  """Match 1 or more.

  TODO: Combine with Star!  Take 0 or 1 as arg.
  """

  def Match(self, tokens, pos, trace):
    results = []
    while True:
      self.log(trace, 'trying')
      result, newpos = self.child.Match(tokens, pos, trace)
      self.log(trace, '-> %r %r', result, newpos)
      if result is None:
        if results:
          return results, newpos
        else:
          return None, pos  # didn't match at least one
      if result is not True:
        results.append(result)
      pos = newpos


class Not(_Single):

  def Match(self, tokens, pos, trace):
    result, _ = self.child.Match(tokens, pos, trace)
    # doesn't consume, so returns same position.
    if result is None:
      return True, pos
    else:
      return None, pos  # NOTE: must be None, not False.


class And(_Single):

  def Match(self, tokens, pos, trace):
    result, _ = self.child.Match(tokens, pos, trace)
    # doesn't consume, so returns same position.
    if result is not None:
      return (True, pos)
    else:
      return (None, pos)


class Ref(Matcher):
  """Match a named expression."""

  # TODO: How to express capturing this?  Wrap it in a node?
  # By default, nodes are themselves.  If there is  RHS, then they are wrapped.

  def __init__(self, name, compiled):
    self.name = name
    self.compiled = compiled

  def __str__(self):
    return '<Ref %s>' % self.name

  def Match(self, tokens, pos, trace):
    # Resolve this at runtime, not compile time.
    matcher = self.compiled[self.name]
    #trace.push()
    #trace.ref('Ref %s', self.name)
    result, pos = matcher.Match(tokens, pos,  trace)
    #trace.ref('-> %s %s', result, pos)
    #trace.pop()
    return result, pos


class RNode(object):
  def __init__(self, node, action):
    """
    Args:
      node: matcher object
      action: function that takes a match output and returns a value.
    """
    self.node = node
    self.action = action

  def Match(self, s, pos, trace):
    result, pos = self.node.Match(s, pos, trace)
    if result is None:
      return None, pos
    else:
      captured = self.action(result)
      return captured, pos

    # interpret the pipeline here


class Trace(object):
  def __init__(self, verbose=False):
    self.verbose = verbose
    self.indent = 0

  def ref(self, msg, *args):
    self._write(msg, *args)

  def log(self, msg, *args):
    if not self.verbose:
      return
    self._write(msg, *args)

  def _write(self, msg, *args):
    if args:
      msg = msg % args
    print (self.indent * ' ') + msg

  def push(self):
    self.indent += 2

  def pop(self):
    self.indent -= 2


def Execute(node, tokens):
#def Execute(node, s, actions):
  """
  Builders: for each type of node, there is a function.
  """
  # For now, just expand it greedily into a list.  We're not taking advantage of
  # the tokenizer yielding tokens.
  if not isinstance(tokens, list):
    tokens = list(tokens)
  assert isinstance(tokens, list), tokens

  # TODO: Remove this.  0 tokens is valid.

  assert tokens, "Empty tokens: %s" % tokens
  trace = Trace()
  #trace = Trace(verbose=True)
  return node.Match(tokens, 0, trace)
